package com.lw.leetcode.back.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 756. 金字塔转换矩阵
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/8 10:06
 */
public class PyramidTransition {


    public static void main(String[] args) {
        PyramidTransition test = new PyramidTransition();

        // true
//        String str = "BCD";
//        String[] arr = {"BCG", "CDE", "GEA", "FFF"};

        // false
//        String str = "AABA";
//        String[] arr = {"AAA", "AAB", "ABA", "ABB", "BAC"};

        // true
//        String str = "BCD";
//        String[] arr = {"ACC","ACB","ABD","DAA","BDC","BDB","DBC","BBD","BBC","DBD","BCC","CDD","ABA","BAB","DDC","CCD","DDA","CCA","DDD"};


        // true
//        String str = "CCC";
//        String[] arr = {"CBB","ACB","ABD","CDB","BDC","CBC","DBA","DBB","CAB","BCB","BCC","BAA","CCD","BDD","DDD","CCA","CAA","CCC","CCB"};

        // false
        String str = "AAAA";
        String[] arr = {"AAB", "AAC", "BCD", "BBE", "DEF"};

        // true
//        String str = "CBDDA";
//        String[] arr = {"ACC","ACA","AAB","BCA","BCB","BAC","BAA","CAC","BDA","CAA","CCA","CCC","CCB",
//                "DAD","CCD","DAB","ACD","DCA","CAD","CBB","ABB","ABC","ABD","BDB","BBC","BBA","DDA","CDD","CBC","CBA","CDA","DBA","ABA"};
        // false
//        String str = "CBA";
//        String[] arr = {"CBV","CBC","CBS","CBA","BAQ"};


        boolean b = test.pyramidTransition(str, Arrays.asList(arr));
        System.out.println(b);
    }


    private Map<String, List<String>> map;

    public boolean pyramidTransition(String bottom, List<String> allowed) {
        Map<String, List<String>> map = new HashMap<>();
        for (String s : allowed) {
            map.computeIfAbsent(s.substring(0, 2), v -> new ArrayList<>()).add(s.substring(2));
        }
        this.map = map;
        return find(bottom, new StringBuilder(), map.get(bottom.substring(0, 2)));
    }

    private boolean find(String str, StringBuilder value, List<String> list) {
        if (str.length() == 1) {
            return true;
        }
        if (list == null) {
            return false;
        }

        for (String s1 : list) {
            value.append(s1);
            int l = value.length();
            if (l == str.length() - 1) {
                if (l == 1) {
                    return true;
                }
                String s = value.toString();
                value.setLength(0);

                boolean b = find(s, value, map.get(s.substring(0, 2)));
                if (b) {
                    return true;
                }
                value.append(s, 0, s.length() - 1);
            } else {
                boolean b = find(str, value, map.get(str.substring(l, l + 2)));
                if (b) {
                    return true;
                }
                value.deleteCharAt(l - 1);
            }
        }
        return false;
    }

}
